/*
 * ThreadSort.java
 * Responsibilities:
 * - create array with random int number
 * - assign the work for each thread
 * - sort the thread
 * - merge the local array from workers
 */
import java.util.*;
import java.text.*;

public class Sort extends Thread {
	private int numThread;
	private int arraySize;
	private int original[], values[];
	private Vector<ThreadSort> worker;
	private TimeStamp ts;
	private boolean debug;
	private Thread t;
	
	public Sort() {
		
	}// end default constructor
	
	public Sort(int numThread, int arraySize, boolean debug, boolean thread) {
		this.debug = debug;
		this.numThread = numThread;
		this.arraySize = arraySize;
		worker = new Vector<ThreadSort>();
		ts = new TimeStamp();
		if(thread) {
			t = new Thread(this);
			t.start();
		}
		else {
			createArray();
			sortArray();
		}
	}// end overload constructor
	
	public void run() {
		createArray();
		sortArray();
	}// end method run
	
	public void createArray() {
		// instantiate 2 integer arrays, load both with same random values
        values = new int[arraySize];
        original = new int[arraySize]; 
        Random r = new Random((long) 77777773);
        for(int i=0; i<arraySize; original[i] = values[i++] = (r.nextInt() % 10000));
       /* if(debug) {
        	String result = "";
    		for(int i = 0; i < values.length; i++)
    			result += values[i] + " ";
    		System.out.println("Array before sort " + result);
        }*/
	}// end method createArray
	
	public void sortArray() {
		if(numThread == 1) {
			ts.start();
			Arrays.sort(values);
			ts.stop();
			printResult();
		}
		else {
			int startIndex, localArraySize;
			ts.start();
			
			for(int tid = 0; tid < numThread; tid++) {
				startIndex = tid *(values.length / numThread);

				// calculate local array size
				if(tid != (numThread - 1))
					localArraySize = values.length / numThread;
				else
					localArraySize = (values.length / numThread) + values.length % numThread;
				
				worker.add(new ThreadSort(tid, values, startIndex, localArraySize));
			}
				// wait for all the threads finish their work
				try {
					for(int i = 0; i<numThread; i++) 
						worker.elementAt(i).getThread().join();
		
				}
				
				catch(InterruptedException e) {	
					System.out.println("Main thread Interrupted");
					e.printStackTrace();
				}
				/* recommend debug when dealing with small array size, otherwise take long time to compute.*/
				/*if(debug) {
					for(int i=0; i<worker.size(); i++)
						System.out.println("thread " + i + " after sorted " + worker.elementAt(i).toString());
				}
				*/
				// merge master array with slave arrays
				int localSize = 0;
				for(int i=0; i<numThread; i++) {
					merge(values, worker.elementAt(i).getLocalArray(), localSize, worker.elementAt(i).getLocalArray().length);
					localSize += worker.elementAt(i).getArraySize();
				}
				ts.stop();
				if(debug) {
					System.out.println("Done sorting the array.");
					printResult();
				}
		}
	}// end method sort
	
	private void merge(int a[],int b[],int aSize,int bSize) {
		int i,j,k;
		int[]c = new int[a.length];
		for(i = 0; i < aSize; i++)
			c[i] = a[i];
		i = 0;j = 0;k = 0;
		while(i < aSize && j < bSize) {
			if(c[i] <= b[j])
				a[k++] = c[i++];
			else
				a[k++] = b[j++];
		}
		while(i < aSize)
			a[k++] = c[i++];
		while(j < bSize)
			a[k++] = b[j++];
	}// end method merge
	
	private String outputFormat(int fieldSize, int intValue) {
        String inum = (new DecimalFormat("0")).format(intValue);
        return ("            ").substring(0,fieldSize-inum.length()) + inum;
    } // end method outputFormat

	private void printResult() {
		DecimalFormat formatter = new DecimalFormat("#,###,###");
		/*
		System.out.println("Array   Original   Sorted  ");
	    System.out.println("Index    Order      Order  ");
	    System.out.println("-----   --------   --------");
	
	    for(int i=0; i<arraySize; i++) 
	        System.out.println(outputFormat(4,i) + outputFormat(10,original[i]) + outputFormat(10,values[i]));
	    */
	    System.out.println("execution time for Sorting workload is: "
	    		+ ts.elapsedTime() + " nanoseconds.");
	    System.out.println();
	}// end method showResult
	
	
	public double getExecutionTime() {
		return this.ts.elapsedTime();
	}// end method getExecutionTime
	
}// end class Sort
